#include "lcs.h"

#include <QList>
#include <iostream>


typedef struct _lcselem {
    int len;
    short type;
} lcselem;

typedef struct _seqitem {
    QChar c;
    short type;
} seqitem;

void printLCS(lcselem **c, const QString &str1, const QString &str2, int i, int j, QList<seqitem> &result)
{
    if (i == 0 && j == 0) {
        return;
    }
    if (i == 0 && j != 0) {
        seqitem item;
        item.c = str2.at(j - 1);
        item.type = 2;
        result.append(item);
        return;
    }
    if (i != 0 && j == 0) {
        seqitem item;
        item.c = str1.at(i - 1);
        item.type = 1;
        result.append(item);
        return;
    }

    if (c[i][j].type == 0) {
        printLCS(c, str1, str2, i - 1, j - 1, result);
        seqitem item;
        item.c = str1.at(i - 1);
        item.type = 0;
        result.append(item);
    }
    else if (c[i][j].type == 1) {
        printLCS(c, str1, str2, i - 1, j, result);
        seqitem item;
        item.c = str1.at(i - 1);
        item.type = 1;
        result.append(item);
    }
    else {
        printLCS(c, str1, str2, i, j - 1, result);
        seqitem item;
        item.c = str2.at(j - 1);
        item.type = 2;
        result.append(item);
    }
}

QString LCS(const QString &str1, const QString &str2)
{
    QString result;
    QList<seqitem> itemvec;

    int m = str1.length();
    int n = str2.length();

    lcselem **c = new lcselem*[m + 1];
    for (int i = 0; i <= m; i++) {
        c[i] = new lcselem[n + 1];
    }

    for (int i = 0; i <= m; i++)
        c[i][0].len = 0;
    for (int j = 0; j <= n; j++)
        c[0][j].len = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1.at(i - 1) == str2.at(j - 1)) {
                c[i][j].len = c[i-1][j-1].len + 1;
                c[i][j].type = 0;
            }
            else if (c[i-1][j].len >= c[i][j-1].len) {
                c[i][j].len = c[i-1][j].len;
                c[i][j].type = 1;
            }
            else {
                c[i][j].len = c[i][j-1].len;
                c[i][j].type = 2;
            }
        }
    }

    printLCS(c, str1, str2, m, n, itemvec);

    for (int i = 0; i <= m; i++)
        delete[] c[i];
    delete[] c;

    int previous_type = 0;
    foreach (seqitem item, itemvec) {
        if (item.type != previous_type) {
            if (previous_type == 1)
                result.append("</bold></font>");
            else if (previous_type == 2)
                result.append("</S></font>");

            if (item.type == 1)
                result.append("<font color='red'><bold>");
            else if (item.type == 2)
                result.append("<font color='blue'><S>");
        }
        result.append(item.c);

        previous_type = item.type;
    }
    if (previous_type == 1)
        result.append("</lack>");
    else if (previous_type == 2)
        result.append("</add>");

    return result;
}
